PittsburghV1, France, Analysis, bibRecord, 000736

A Feasibility Pump for mixed integer nonlinear programs

Identifieur interne : 000736 ( France/Analysis ); précédent : 000735; suivant : 000737

A Feasibility Pump for mixed integer nonlinear programs

Auteurs : Pierre Bonami [France] ; Gérard Cornuéjols [France] ; Andrea Lodi [Italie] ; François Margot [États-Unis]

Source :

RBID : Hal:hal-00421755

Abstract

We present an algorithm for finding a feasible solution to a convex mixed integer nonlinear program. This algorithm, called Feasibility Pump, alternates between solving nonlinear programs and mixed integer linear programs. We also discuss how the algorithm can be iterated so as to improve the first solution it finds, as well as its integration within an outer approximation scheme. We report computational results.

Url:

https://hal.archives-ouvertes.fr/hal-00421755

DOI: 10.1007/s10107-008-0212-2

Affiliations:

France, Italie, États-Unis

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: 000018
to stream Hal, to step Curation: 000018
to stream Hal, to step Checkpoint: 000552
to stream Main, to step Merge: 00AF64
to stream Main, to step Curation: 00A812
to stream Main, to step Exploration: 00A812
to stream France, to step Extraction: 000736

Links to Exploration step

Hal:hal-00421755

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">A Feasibility Pump for mixed integer nonlinear programs</title>
<author><name sortKey="Bonami, Pierre" sort="Bonami, Pierre" uniqKey="Bonami P" first="Pierre" last="Bonami">Pierre Bonami</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-862" status="OLD">          <idno type="RNSR">200212226K</idno>
          <orgName>Laboratoire d'informatique Fondamentale de Marseille - UMR 6166</orgName>
          <orgName type="acronym">LIF</orgName>
          <date type="start">2002</date>
          <date type="end">2011</date>
          <desc>            <address>              <addrLine>CMI 39, Rue Joliot Curie 13453 MARSEILLE CEDEX 13</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.lif.univ-mrs.fr/</ref>
          </desc>
          <listRelation>            <relation active="#struct-5033" type="direct"></relation>
            <relation active="#struct-92823" type="direct"></relation>
            <relation name="UMR6166" active="#struct-441569" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-5033" type="direct"><org type="institution" xml:id="struct-5033" status="OLD">          <idno type="IdRef">026402882</idno>
          <orgName>Université de la Méditerranée - Aix-Marseille 2</orgName>
          <date type="start">1969</date>
          <date type="end">2011</date>
          <desc>            <address>              <addrLine>58, boulevard Charles Livon - 13284 Marseille cedex 07</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univmed.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-92823" type="direct"><org type="institution" xml:id="struct-92823" status="OLD">          <idno type="IdRef">026403781</idno>
          <orgName>Université de Provence - Aix-Marseille 1</orgName>
          <date type="end">2011-12-31</date>
          <desc>            <address>              <addrLine>3, place Victor Hugo - 13331 Marseille Cedex 03</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-provence.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle name="UMR6166" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Cornuejols, Gerard" sort="Cornuejols, Gerard" uniqKey="Cornuejols G" first="Gérard" last="Cornuéjols">Gérard Cornuéjols</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-862" status="OLD">          <idno type="RNSR">200212226K</idno>
          <orgName>Laboratoire d'informatique Fondamentale de Marseille - UMR 6166</orgName>
          <orgName type="acronym">LIF</orgName>
          <date type="start">2002</date>
          <date type="end">2011</date>
          <desc>            <address>              <addrLine>CMI 39, Rue Joliot Curie 13453 MARSEILLE CEDEX 13</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.lif.univ-mrs.fr/</ref>
          </desc>
          <listRelation>            <relation active="#struct-5033" type="direct"></relation>
            <relation active="#struct-92823" type="direct"></relation>
            <relation name="UMR6166" active="#struct-441569" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-5033" type="direct"><org type="institution" xml:id="struct-5033" status="OLD">          <idno type="IdRef">026402882</idno>
          <orgName>Université de la Méditerranée - Aix-Marseille 2</orgName>
          <date type="start">1969</date>
          <date type="end">2011</date>
          <desc>            <address>              <addrLine>58, boulevard Charles Livon - 13284 Marseille cedex 07</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univmed.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-92823" type="direct"><org type="institution" xml:id="struct-92823" status="OLD">          <idno type="IdRef">026403781</idno>
          <orgName>Université de Provence - Aix-Marseille 1</orgName>
          <date type="end">2011-12-31</date>
          <desc>            <address>              <addrLine>3, place Victor Hugo - 13331 Marseille Cedex 03</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-provence.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle name="UMR6166" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Lodi, Andrea" sort="Lodi, Andrea" uniqKey="Lodi A" first="Andrea" last="Lodi">Andrea Lodi</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-102250" status="INCOMING">          <orgName>Dipartimento di Elettronica, Informatica e Sistemistica</orgName>
          <orgName type="acronym">DEIS</orgName>
          <desc>            <address>              <addrLine>University of Bologna Viale Risorgimento, 2 40136 Bologna, Italy</addrLine>
              <country key="IT"></country>
            </address>
            <ref type="url">http://www.or.deis.unibo.it/</ref>
          </desc>
          <listRelation>            <relation active="#struct-30978" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-30978" type="direct"><org type="institution" xml:id="struct-30978" status="VALID">          <orgName>Università di Bologna [Bologna]</orgName>
          <orgName type="acronym">UNIBO</orgName>
          <desc>            <address>              <addrLine>Via Zamboni, 33 - 40126 Bologna</addrLine>
              <country key="IT"></country>
            </address>
            <ref type="url">http://www.eng.unibo.it/PortaleEn/default.htm</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Italie</country>
</affiliation>
</author>
<author><name sortKey="Margot, Francois" sort="Margot, Francois" uniqKey="Margot F" first="François" last="Margot">François Margot</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87848" status="VALID">          <orgName>Tepper School of Business</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave., Pittsburgh, PA 15213, USA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.tepper.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-67135" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-67135" type="direct"><org type="institution" xml:id="struct-67135" status="VALID">          <orgName>Carnegie Mellon University [Pittsburgh]</orgName>
          <orgName type="acronym">CMU</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave,  Pittsburgh, PA 15213</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cmu.edu/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00421755</idno>
<idno type="halId">hal-00421755</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00421755</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00421755</idno>
<idno type="doi">10.1007/s10107-008-0212-2</idno>
<date when="2008-03-18">2008-03-18</date>
<idno type="wicri:Area/Hal/Corpus">000018</idno>
<idno type="wicri:Area/Hal/Curation">000018</idno>
<idno type="wicri:Area/Hal/Checkpoint">000552</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000552</idno>
<idno type="wicri:Area/Main/Merge">00AF64</idno>
<idno type="wicri:Area/Main/Curation">00A812</idno>
<idno type="wicri:Area/Main/Exploration">00A812</idno>
<idno type="wicri:Area/France/Extraction">000736</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">A Feasibility Pump for mixed integer nonlinear programs</title>
<author><name sortKey="Bonami, Pierre" sort="Bonami, Pierre" uniqKey="Bonami P" first="Pierre" last="Bonami">Pierre Bonami</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-862" status="OLD">          <idno type="RNSR">200212226K</idno>
          <orgName>Laboratoire d'informatique Fondamentale de Marseille - UMR 6166</orgName>
          <orgName type="acronym">LIF</orgName>
          <date type="start">2002</date>
          <date type="end">2011</date>
          <desc>            <address>              <addrLine>CMI 39, Rue Joliot Curie 13453 MARSEILLE CEDEX 13</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.lif.univ-mrs.fr/</ref>
          </desc>
          <listRelation>            <relation active="#struct-5033" type="direct"></relation>
            <relation active="#struct-92823" type="direct"></relation>
            <relation name="UMR6166" active="#struct-441569" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-5033" type="direct"><org type="institution" xml:id="struct-5033" status="OLD">          <idno type="IdRef">026402882</idno>
          <orgName>Université de la Méditerranée - Aix-Marseille 2</orgName>
          <date type="start">1969</date>
          <date type="end">2011</date>
          <desc>            <address>              <addrLine>58, boulevard Charles Livon - 13284 Marseille cedex 07</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univmed.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-92823" type="direct"><org type="institution" xml:id="struct-92823" status="OLD">          <idno type="IdRef">026403781</idno>
          <orgName>Université de Provence - Aix-Marseille 1</orgName>
          <date type="end">2011-12-31</date>
          <desc>            <address>              <addrLine>3, place Victor Hugo - 13331 Marseille Cedex 03</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-provence.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle name="UMR6166" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Cornuejols, Gerard" sort="Cornuejols, Gerard" uniqKey="Cornuejols G" first="Gérard" last="Cornuéjols">Gérard Cornuéjols</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-862" status="OLD">          <idno type="RNSR">200212226K</idno>
          <orgName>Laboratoire d'informatique Fondamentale de Marseille - UMR 6166</orgName>
          <orgName type="acronym">LIF</orgName>
          <date type="start">2002</date>
          <date type="end">2011</date>
          <desc>            <address>              <addrLine>CMI 39, Rue Joliot Curie 13453 MARSEILLE CEDEX 13</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.lif.univ-mrs.fr/</ref>
          </desc>
          <listRelation>            <relation active="#struct-5033" type="direct"></relation>
            <relation active="#struct-92823" type="direct"></relation>
            <relation name="UMR6166" active="#struct-441569" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-5033" type="direct"><org type="institution" xml:id="struct-5033" status="OLD">          <idno type="IdRef">026402882</idno>
          <orgName>Université de la Méditerranée - Aix-Marseille 2</orgName>
          <date type="start">1969</date>
          <date type="end">2011</date>
          <desc>            <address>              <addrLine>58, boulevard Charles Livon - 13284 Marseille cedex 07</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univmed.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-92823" type="direct"><org type="institution" xml:id="struct-92823" status="OLD">          <idno type="IdRef">026403781</idno>
          <orgName>Université de Provence - Aix-Marseille 1</orgName>
          <date type="end">2011-12-31</date>
          <desc>            <address>              <addrLine>3, place Victor Hugo - 13331 Marseille Cedex 03</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-provence.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle name="UMR6166" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Lodi, Andrea" sort="Lodi, Andrea" uniqKey="Lodi A" first="Andrea" last="Lodi">Andrea Lodi</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-102250" status="INCOMING">          <orgName>Dipartimento di Elettronica, Informatica e Sistemistica</orgName>
          <orgName type="acronym">DEIS</orgName>
          <desc>            <address>              <addrLine>University of Bologna Viale Risorgimento, 2 40136 Bologna, Italy</addrLine>
              <country key="IT"></country>
            </address>
            <ref type="url">http://www.or.deis.unibo.it/</ref>
          </desc>
          <listRelation>            <relation active="#struct-30978" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-30978" type="direct"><org type="institution" xml:id="struct-30978" status="VALID">          <orgName>Università di Bologna [Bologna]</orgName>
          <orgName type="acronym">UNIBO</orgName>
          <desc>            <address>              <addrLine>Via Zamboni, 33 - 40126 Bologna</addrLine>
              <country key="IT"></country>
            </address>
            <ref type="url">http://www.eng.unibo.it/PortaleEn/default.htm</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Italie</country>
</affiliation>
</author>
<author><name sortKey="Margot, Francois" sort="Margot, Francois" uniqKey="Margot F" first="François" last="Margot">François Margot</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87848" status="VALID">          <orgName>Tepper School of Business</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave., Pittsburgh, PA 15213, USA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.tepper.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-67135" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-67135" type="direct"><org type="institution" xml:id="struct-67135" status="VALID">          <orgName>Carnegie Mellon University [Pittsburgh]</orgName>
          <orgName type="acronym">CMU</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave,  Pittsburgh, PA 15213</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cmu.edu/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
</analytic>
<idno type="DOI">10.1007/s10107-008-0212-2</idno>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We present an algorithm for finding a feasible solution to a convex mixed integer nonlinear program. This algorithm, called Feasibility Pump, alternates between solving nonlinear programs and mixed integer linear programs. We also discuss how the algorithm can be iterated so as to improve the first solution it finds, as well as its integration within an outer approximation scheme. We report computational results.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>Italie</li>
<li>États-Unis</li>
</country>
</list>
<tree><country name="France"><noRegion><name sortKey="Bonami, Pierre" sort="Bonami, Pierre" uniqKey="Bonami P" first="Pierre" last="Bonami">Pierre Bonami</name>
</noRegion>
<name sortKey="Cornuejols, Gerard" sort="Cornuejols, Gerard" uniqKey="Cornuejols G" first="Gérard" last="Cornuéjols">Gérard Cornuéjols</name>
</country>
<country name="Italie"><noRegion><name sortKey="Lodi, Andrea" sort="Lodi, Andrea" uniqKey="Lodi A" first="Andrea" last="Lodi">Andrea Lodi</name>
</noRegion>
</country>
<country name="États-Unis"><noRegion><name sortKey="Margot, Francois" sort="Margot, Francois" uniqKey="Margot F" first="François" last="Margot">François Margot</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/France/Analysis

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000736 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 000736 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Amérique
   |area=    PittsburghV1
   |flux=    France
   |étape=   Analysis
   |type=    RBID
   |clé=     Hal:hal-00421755
   |texte=   A Feasibility Pump for mixed integer nonlinear programs
}}

This area was generated with Dilib version V0.6.38.
Data generation: Fri Jun 18 17:37:45 2021. Site generation: Fri Jun 18 18:15:47 2021

	Serveur d'exploration sur Pittsburgh
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur Pittsburgh

A Feasibility Pump for mixed integer nonlinear programs

A Feasibility Pump for mixed integer nonlinear programs

Source :

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri